package com.liyunhan.LevenshteinDistance;

/**
 * @Description: 字符串的最小编辑距离(Levenshtein 距离), 此处为将A串变为B串
 * @Author: Liyunhan
 * @Date: 2021/11/23 21:23
 */
public class myLevenshtein {
    //字符串A
    private StringBuilder strA;
    //字符串B
    private StringBuilder strB;

    /**
     * 提供带参构造器, 要求传入字符串A和字符串B
     *
     * @param strA
     * @param strB
     */
    public myLevenshtein(StringBuilder strA, StringBuilder strB) {
        this.strA = strA;
        this.strB = strB;
    }

    /**
     * 提供无参构造器, 方便测试代码用
     */
    public myLevenshtein() {
        this.strA = new StringBuilder("Lyhn");
        this.strB = new StringBuilder("Liyunhan");
    }

    /**
     * 算法主体实现
     *
     * @return
     */
    public int theAlgorithm() {
        int len_A = strA.length();
        int len_B = strB.length();
        //编辑距离二维数组
        int[][] edit = new int[len_B + 1][len_A + 1];
        //两串均为空值时
        edit[0][0] = 0;
        //A串为空, B串不空时
        for (int i = 1; i <= len_A; i++) {
            //此时编辑距离取决于B串长度
            edit[0][i] = i;
        }
        //A串不空, B串为空时(删除操作)
        for (int i = 1; i <= len_B; i++) {
            edit[i][0] = i;
        }
        //A, B串都不为空时
        for (int i = 1; i <= len_B; i++) {
            for (int j = 1; j <= len_A; j++) {
                edit[i][j] = getMinValue(getMinValue(edit[i - 1][j] + 1, edit[i][j - 1] + 1),
                        (strA.charAt(j - 1) == strB.charAt(i - 1) ? edit[i - 1][j - 1] : edit[i - 1][j - 1] + 1));
            }
        }

        return edit[len_B][len_A];

    }

    /**
     * 获取两整数中较小值方法
     *
     * @param a
     * @param b
     * @return
     */
    private int getMinValue(int a, int b) {
        return a > b ? b : a;
    }

    /**
     * getter & setter
     *
     * @return
     */
    public StringBuilder getStrA() {
        return strA;
    }

    public void setStrA(StringBuilder strA) {
        this.strA = strA;
    }

    public StringBuilder getStrB() {
        return strB;
    }

    public void StringBuilder(StringBuilder strB) {
        this.strB = strB;
    }
}
